//BNB
//$Id: bnb_common.h 692 2011-03-28 17:18:49Z Oleg.Bulychov $
#pragma once

//__________________________________________________________________________________
#include "src/heo/include/random.h"
#include "src/heo/include/stream_visitor.h"
#include "src/heo/include/xml_file.h"
#include "src/heo/include/optimization_direction.h"
#include "src/heo/include/solution.h"
#include "src/heo/include/stop_condition.h"
#include "src/heo/include/alloc_page.h"
#include "src/heo/include/alloc_lite.h"
#include "src/heo/include/alloc_big.h"
#include "src/heo/include/big_vector.h"
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
template<class Env,
         class Task,
         class Params,
         class Predictor,
         class BoundPredicate>
struct BNB_Traits
{
    typedef Env             TEnvironment;
    typedef Task            TTask;
    typedef Params          TParams;
    typedef Predictor       TPredictor;
    typedef BoundPredicate  TBoundPredicate;//minimization == <
};
//__________________________________________________________________________________
struct bnb_tag
{};
//__________________________________________________________________________________
struct BNB_Statistics
{
public:
    size_t nodes_;
    size_t pruned_;
    size_t sent_;
    size_t received_;
    size_t pq_max_size_;
    size_t idle_;
//.............................................................................
    explicit BNB_Statistics(): nodes_(), pruned_(), sent_(), received_(),
        pq_max_size_(), idle_()
    {}
//.............................................................................
    void dump(std::ostream& os) const
    {
        os << "Nodes generated: " << nodes_
           << ", pruned: " << pruned_
           << ", sent: " << sent_
           << ", received: " << received_
           << "; PQ max size: " << pq_max_size_
           << "; idle: " << idle_
           << lf;
   }
};
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
template<class T>
class BNB
{
    DISALLOW_COPY_AND_ASSIGN(BNB);
public:
    typedef typename T::TEnvironment    TEnvironment;
    typedef typename T::TTask           TTask;
    typedef typename T::TParams         TParams;
    typedef typename T::TPredictor      TPredictor;
    typedef typename T::TBoundPredicate TBoundPredicate;

    typedef solution<typename TEnvironment::TSolution, bnb_tag> TSolution;

    typedef typename TSolution::TDirection TDirection;
    typedef typename TSolution::TCostType  TCostType;

    typedef big_sorted_vector< ref_ptr<TTask>, typename TTask::LessPriority> TPriorityQueue;

    typedef typename TEnvironment::TSolution TInOutSolution;
    typedef typename TEnvironment::TStatistics TStatistics;
public://TODO review
    TEnvironment*           env_;
    int                     rank_;
    random_generator          rnd_;

    std::vector< ref_ptr< stop_condition::abstract_stop_condition<TEnvironment,
        TSolution> > > stop_condition_;
    int                     max_step_;

    TPredictor              predictor_;

    TPriorityQueue          pq_;
    TSolution               current_;
    TCostType               first_ub_;
    TCostType               best_ub_;
    int                     local_ub_changed_;

    bool                    debug_flag_;

    TParams                 params_;
    BNB_Statistics          stat_;
public:
    explicit BNB(): env_(NULL),
        rank_(0),
        rnd_(0),
        max_step_(0),
        first_ub_(),
        best_ub_(),
        local_ub_changed_(),
        debug_flag_()
    {
        stop_condition::max_step<TEnvironment, TSolution>::instantiate();
        stop_condition::cost_limit<TEnvironment, TSolution>::instantiate();
        hidden::instantiate_ptr_visit((stop_condition::max_step<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
        hidden::instantiate_ptr_visit((stop_condition::cost_limit<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
    }

    static char const* get_Name() { return "bnb"; }
    static char const* get_Section() { return get_Name(); }

    template<class V>
    void accept(V& v)
    {
        v(params_);
        v(VAR_(stop_condition),             stop_condition::validator<
            stop_condition::max_step<TEnvironment, TSolution> >());
    }

    TEnvironment* get_Environment() const { return env_; }

    int get_Rank() const { return rank_; }

    random_generator& get_Rnd() { return rnd_; }

    void init(TEnvironment* env, int rank, int thread_id, bool debug_flag = false)
    {
        if (!env_)
        {
            env_ = env;
            rank_ = rank;
            rnd_.set_Thread_Id(thread_id);
            current_.init(env_, rnd_);
            debug_flag_ = debug_flag;
        }
        else
        {
            ASSERT_(env_ == env);
            ASSERT_(rank_ == rank);
        }
    }

    template<class TInSolution>
    void set_Initial_Solution(TInSolution const& sol)
    {
        current_.assign(sol);
        current_.evaluate(env_, rnd_);
    }

    void init_From_Pool(Solution_Pool<TInOutSolution>& pool)
    {
        if (pool.sol_list_.empty())
        {
            current_.init(env_, rnd_);
            current_.generate(env_, rnd_);
        }
        else
        {
            size_t idx = rank_ % pool.sol_list_.size();
            current_.assign(pool.sol_list_[idx]);
        }
        current_.evaluate(env_, rnd_);
    }

    TSolution& get_Final_Solution()
    {
        return current_;
    }

    bool stop(int nStep)
    {
        TCostType best_cost = get_Final_Solution().get_Cost();
        for (size_t i = 0; i < stop_condition_.size(); ++i)
        {
            if (stop_condition_[i]->stop(*env_, best_cost, nStep))
                return true;
        }
        return false;
    }

    int get_Debug_Level() const
    {
        int level = env_->debug_level_;
        if (debug_flag_)
            level = (env_->debug_level_ >> 16);
        return level;
    }

    void calc_Max_Step()
    {
        max_step_ = std::numeric_limits<int>::max();
        for (size_t i = 0; i < stop_condition_.size(); ++i)
        {
            int t = stop_condition_[i]->get_Max_Step();
            if (t < max_step_)
                max_step_ = t;
        }
    }

    template<class V>
    void recv_Task(V& in)
    {
        ref_ptr<TTask> t;
        t.attach(new TTask);
        t->init(env_, rnd_);
        in >> *t;
        pq_.push(t);
    }

    template<class V>
    void send_Task(size_t id, V& out)
    {
        out << *(pq_[id]);
    }

    enum
    {
        BNB_CONTINUE = 0,
        BNB_PQ_EMPTY,
        BNB_STOP,
        BNB_ERROR,
        BNB_IDLE
    };

    void show_Status(int r, int step)
    {
        if (rank_ >= get_Debug_Level())
            return;
#pragma omp critical(debug_output)
        {
            if (rank_ > 0)
                sys_api::Set_Console_Color(rank_ % 15 + 1);
            std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step;
            switch(r)
            {
            case BNB_PQ_EMPTY:
                std::cout << ": PQ empty" << lf;
                break;
            case BNB_STOP:
                std::cout << ": stop" << lf;
                break;
            case BNB_ERROR:
                std::cout << ": ERROR" << lf;
                break;
            case BNB_IDLE:
                std::cout << ": IDLE" << lf;
                break;
            }
            if (rank_ > 0)
                std::cout << no_color;
        }
    }

    int do_Step(int step)
    {
        sweep_PQ_Top();
        if (pq_.is_Empty())
            return BNB_PQ_EMPTY;

        ref_ptr<TTask> task;
        task = pq_.top();
        pq_.pop();

        //:LB should be < UB for minimization
        ASSERT_(TBoundPredicate()(task->get_LB(), best_ub_));

        if (rank_ < get_Debug_Level())
            task->show_Progress(*this, step);
        if (!branch(task, predictor_, step))
            return BNB_ERROR;

        if (stop(step))
            return BNB_STOP;
        return BNB_CONTINUE;
    }

    void solve(TInOutSolution& sol, TStatistics& stat)
    {
        set_Initial_Solution(sol);
        solve_Impl(stat);
        sol.assign(get_Final_Solution());
    }

    void solve(Solution_Pool<TInOutSolution>& pool, TStatistics& stat)
    {
        init_From_Pool(pool);

        solve_Impl(stat);

        update_Pool(pool);
    }

    void solve_Impl(TStatistics& stat)
    {
        calc_Max_Step();

        first_ub_ = best_ub_ = current_.get_Ub(env_);
        predictor_.init(env_, rnd_);
        predictor_.pre_Calculate(env_, rnd_);

        ref_ptr<TTask> root;
        root.attach(new TTask);
        root->init(env_, rnd_);
        pq_.push(root);
        stat.update(0, rank_, *this, env_);

        for (int step = 1; ; ++step)
        {
            int r = do_Step(step);
            stat.update(step, rank_, *this, env_);
            if (r != (int)BNB_CONTINUE)
            {
                show_Status(r, step);
                break;
            }
        }
    }

    void update_Pool(Solution_Pool<TInOutSolution>& pool)
    {
        pool.sol_list_.resize(1);

        TSolution const& final_sol = get_Final_Solution();
        //:final_sol --> pool

        TInOutSolution& it = pool.sol_list_[0];
        it.init(env_, rnd_);
        it.assign(final_sol);

        if (get_Debug_Level())
        {
            std::cout << lf
                << this->rank_ << ": final cost = " << final_sol.get_Cost() << lf;
        }
    }

    bool branch(ref_ptr<TTask>& task, TPredictor& pred, int step)
    {
        TCostType prev_ub = best_ub_;
        if (!task->branch(*this,
            pred,
            task,
            step))
        {
            return false;
        }
        if (best_ub_ != prev_ub)
        {
            local_ub_changed_ = 1;
            sweep_PQ();
        }
        if (pq_.size() > stat_.pq_max_size_)
            stat_.pq_max_size_ = pq_.size();
        return true;
    }

    size_t num_Valid_Items() const
    {
        size_t k = 0;
        for(size_t i = 0; i < pq_.size(); ++i)
        {
            if (TBoundPredicate()(pq_[i]->get_LB(), best_ub_))
                ++k;
        }
        return k;
    }

    void sweep_PQ()
    {
#if defined(_DEBUG)
        size_t tmp = num_Valid_Items();
#endif
        //:erase(remove_if())
        size_t pruned = 0;
        for(size_t i = 0; i < pq_.size(); ++i)
        {
            if (!TBoundPredicate()(pq_[i]->get_LB(), best_ub_))//TODO +epsilon?
            {
                size_t j = i + 1;
                for(; j < pq_.size(); ++j)
                {
                    if (TBoundPredicate()(pq_[j]->get_LB(), best_ub_))
                        break;
                }
                pruned += j - i;
                pq_.erase(i, j - i);
            }
        }
        ASSERT_(num_Valid_Items() == tmp);
        ASSERT_(tmp == pq_.size());
        stat_.pruned_ += pruned;
    }

    void sweep_PQ_Top()
    {
        if (pq_.is_Empty())
            return;

#if defined(_DEBUG)
        size_t tmp = num_Valid_Items();
#endif

        size_t pruned = 0;
        size_t i = pq_.size() - 1;

        if (!TBoundPredicate()(pq_[i]->get_LB(), best_ub_))
        {
            size_t j = i;
            for(; i > 0; --i)
            {
                if (TBoundPredicate()(pq_[i - 1]->get_LB(), best_ub_))
                    break;
            }
            pruned += j - i + 1;
            pq_.erase(i, j - i + 1);
        }

        ASSERT_(num_Valid_Items() == tmp);
        stat_.pruned_ += pruned;
    }
};
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________

//EOF!
